
const CASHES: [u32; 8] = [1, 2, 5, 10, 20, 30, 50, 100];

pub fn dp_rec_mc(amount: u32) -> u32 {
    //  这里写逻辑
    // todo!()

    let mut amount = amount;
    let mut result: std::collections::HashMap<u32, u32> = std::collections::HashMap::new();
    // 贪心算法
    for &greed in CASHES.iter().rev() {
        
        if amount == 0 {
            break;
        }
        // 每次先用最大的面额换
        let count = amount / greed;
        if count > 0 {
            result.insert(greed, count);
            amount -= count * greed;
        }
    }
    result.values().sum()
}
